package org.lql.algo.codecrush.hot100.doublePointer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author: liangqinglong
 * @date: 2025-09-08 11:21
 * @description: 15. 三数之和 <a href="https://leetcode.cn/problems/3sum/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
 **/
public class ThreeSum {

	public List<List<Integer>> threeSum(int[] nums) {
		Arrays.sort(nums);
		List<List<Integer>> ans = new ArrayList<>();
		for (int i = 0; i < nums.length; i++) {
			if (i > 0 && nums[i] == nums[i - 1]) {
				continue;
			}
			List<List<Integer>> lists = twoSum(nums, i + 1, -nums[i]);
			for (List<Integer> list : lists) {
				ans.add(Arrays.asList(nums[i], list.get(0), list.get(1)));
			}
		}
		return ans;
	}

	private List<List<Integer>> twoSum(int[] numbers, int start, int target) {
		List<List<Integer>> ans = new ArrayList<>();
		int j = numbers.length - 1;
		for (int i = start; i < numbers.length; i++) {
			if (i > start && numbers[i] == numbers[i - 1]) {
				continue;
			}
			while (i < j && numbers[i] + numbers[j] > target) {
				j--;
			}
			if (i < j && numbers[i] + numbers[j] == target) {
				ans.add(Arrays.asList(numbers[i], numbers[j]));
			}
		}
		return ans;
	}

	public static void main(String[] args) {
		// [[-1,-1,2],[-1,0,1]]
		System.out.println(new ThreeSum().threeSum(new int[]{-1, 0, 1, 2, -1, -4}));
		// []
		System.out.println(new ThreeSum().threeSum(new int[]{0, 1, 1}));
		// [[0,0,0]]
		System.out.println(new ThreeSum().threeSum(new int[]{0, 0, 0}));
	}
}
